
//# Bit Shifter

// This module is a building block for application-specific shifts and
// rotates. It synthesizes to LUT logic and can be quite large if not
// specialized to a particular situation.

//## A Warning About Shift Right and Signed Division

// While a left shift by N is always equivalent to a multiplication by
// 2<sup>N</sup> for both signed and unsigned binary integers, an arithmetic
// shift right by N is only a truncating division by 2<sup>N</sup> for
// *positive* binary integers. For negative integers, the result is so-called
// modulus division, and the quotient ends up off by one in magnitude, and
// must be corrected by adding +1, *but only if an odd number results as part
// of the intermediate division steps*. That is, if a non-zero bit was shifted
// out to the right.

// To implement proper signed division by a power-of-two, use the <a
// href="./Divider_Integer_Signed_by_Powers_of_Two.html">Integer Divider by
// Power of Two</a> module, which performs the correction for negative
// numbers and also calculates the remainder as a bonus.

//## Usage

// We can treat the `shift_amount` and the `shift_direction` together as
// a signed magnitude number: the amount is an absolute value, and the
// direction is the sign of the value. Here, a `shift_direction` of `1`,
// meaning a negative number, shifts to the right. Choosing this convention
// for the sign matches the behaviour of a shift when we think about it as
// a multiplication or division by a power of 2:

// * Multipliying by 8 is equivalent to 2<sup>3</sup>N, which is
// a shift-left by 3 steps.
// * Dividing N by 4 is equivalent to 2<sup>-2</sup>N, which is
// a shift-right by 2 steps.

// Adding together these multiples and fractions generated by the shifts
// enables the creation of small, cheap scaling by constant ratios:

// * 3N = N + 2<sup>1</sup>N
// * 10N = 8N + 2N = 2<sup>3</sup>N + 2<sup>1</sup>N
// * 5N/4 = N + N/4 = N + 2<sup>-2</sup>N
// * etc...

// When the shift values are constant, the shifter reduces to simple rewiring,
// which in turn reduces the above examples to an adder or two each.

// The shifts are internally unsigned and `word_in` and `word_out` are
// extended to the left and right so new bits can be shifted in and current
// bits shifted out without loss, regardless of shift amount or direction,
// which enables the creation of more complex shifts or rotates:

// * Wire the most-significant bit (MSB) of `word_in` to all `word_in_left` inputs and zero to all `word_in_right` inputs to create a signed arithmetic shift.
// * Wire the `word_in` MSB to `word_in_right` MSB (or vice-versa) to create a rotate function.
// * Feed `word_out_left` and `word_out` to a double-word adder and set the
// shift to +1 (left by 1) as part of the construction of a conditional-add
// multiplier, which multiplies two N-bit words in N cycles, giving a 2N-bit
// result.

`default_nettype none

module Bit_Shifter
#(
    parameter   WORD_WIDTH  = 0
)
(
    input   wire    [WORD_WIDTH-1:0]    word_in_left,
    input   wire    [WORD_WIDTH-1:0]    word_in,
    input   wire    [WORD_WIDTH-1:0]    word_in_right,

    input   wire    [WORD_WIDTH-1:0]    shift_amount,
    input   wire                        shift_direction, // 0/1 -> left/right

    output  reg     [WORD_WIDTH-1:0]    word_out_left,
    output  reg     [WORD_WIDTH-1:0]    word_out,
    output  reg     [WORD_WIDTH-1:0]    word_out_right
);

// Let's document the shift direction convention again here, and define our
// initial values for the outputs and the intermediate result.

    localparam  LEFT_SHIFT  = 1'b0;
    localparam  RIGHT_SHIFT = 1'b1;

    localparam  TOTAL_WIDTH = WORD_WIDTH * 3;
    localparam  TOTAL_ZERO  = {TOTAL_WIDTH{1'b0}};
    localparam  WORD_ZERO   = {WORD_WIDTH{1'b0}};

    initial begin
        word_out_left    = WORD_ZERO;
        word_out         = WORD_ZERO;
        word_out_right   = WORD_ZERO;
    end 

    reg [TOTAL_WIDTH-1:0] word_in_total = TOTAL_ZERO;

// Rather than do arithmetic and calculate slices of vectors to figure out
// where the shifted bits end up, let's concatenate the input words into one
// triple-wide word, shift it as an unsigned number, then deconcatenate the
// result into each output word. All we have to do is keep the same convention
// on bit significance: here LSB is on the right.

    always @(*) begin
        word_in_total = {word_in_left, word_in, word_in_right};
        {word_out_left, word_out, word_out_right} = (shift_direction == LEFT_SHIFT) ? word_in_total << shift_amount : word_in_total >> shift_amount; 
    end

endmodule

